import java.util.Arrays;
import java.util.Stack;

public class MyStack {
    //定义一个数组来代表栈
    public int[]elem;
    public  int usedSize;
    public MyStack(){
        elem=new int[10];
    }
    public void push(int val){
        if (isFull()){
            //如果满了就扩容
            elem= Arrays.copyOf(elem,2*elem.length); }
            elem[usedSize]=val;
            usedSize++;

    }
    public boolean isFull(){
        return usedSize==elem.length;//如果相同返回1，不同返回0
    }
    public boolean empty(){
        return usedSize==0;
    }
    public int pop(){
        if (empty()){
            return -1;//如果数真的是-1怎么办
        }
        int oldVal=elem[usedSize-1];
        usedSize--;//变相删除，下次存数就存在被删除的pop的位置了
        return oldVal;
    }
    public int peek(){//获取栈顶值
        if (empty()){
            return -1;//如果数真的是-1怎么办
        }

        return elem[usedSize-1];
    }
    //括号匹配
    //给定一个只包括“（” “）”  “【”  “】”  “{”  “}”的字符串s，判断字符串是否有效,匹配的话返回true,不匹配的话返回false
    public boolean isValid(String s){
        Stack<Character>stack=new Stack<>();
        for (int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            //如果是左括号的话，就入栈
            if (ch=='('||ch=='['||ch=='{'){
                stack.push(ch);
            }else {
                //如果不是左括号就进行别的操作（判断）
                if (stack.empty()){//字符串还有但是栈空了，肯定不匹配
                    return false;
                }else {
                    //取栈顶元素和当前的右括号进行比较，如果全部相等，那么返回true，如果有1个不相等就返回false
                    char chL=stack.peek();//peek一下栈顶元素
                    if (chL=='('&&ch==')'||chL=='['&&ch==']'||chL=='{'&&ch=='}'){
                        //代表这个元素是匹配的
                        stack.pop();
                    }else {
                        //当前括号不匹配
                        return  false;
                    }

                }

            }
        }
        return stack.empty();//栈是空的话返回true，栈里面有元素就返回false（右括号遍历完了，但是栈里面还有元素的话，肯定不匹配）
    }
//给你一个字符串数组，表示一个根据逆波兰表达式表示的算术表达式
    //给的是一个后缀表达式，(一个数组)求出最后的计算结果

    public  int evalRPN(String[]tokens){//方法：碰到数就入栈，碰到操作符就弹出两个数按顺序进行运算，最后返回栈里面的数
        Stack<Integer>stack=new Stack<>();
        for (int i=0;i<tokens.length;i++){
            String tmp=tokens[i];//取出数组里面的元素
            if (!isOpearation(tmp)){
                //如果不是操作数就入栈，但是注意是一个字符数组，得转整数
                Integer val=Integer.valueOf(tmp);
                stack.push(val);
            }else {//如果是操作符就进行运算
                //先弹出两个数
                Integer val2=stack.pop();
                Integer val1=stack.pop();
                switch (tmp){
                    case"+":
                        stack.push(val1+val2);
                        break;
                    case"-":
                        stack.push(val1-val2);
                        break;
                    case "*":
                        stack.push(val1*val2);
                        break;
                    case "/":
                        stack.push(val1/val2);
                        break;
                }
        }
    }
        //等这个循环走完了，直接返回栈里面最后一个数
        return stack.pop();


}
public  boolean isOpearation(String s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;

        }
        return false;
    }
//输入两个整数序列，第一个序列表示栈的压入序列，请判断第二个序列是否为该栈的弹出序列，假如压入栈的所有数字均不相等
    public boolean isPopOrder(int[]pushV,int[]popV){
        int j=0;
        Stack<Integer>stack=new Stack<>();
        for (int i=0;i< pushV.length;i++){//定义一个i遍历压入序列，j遍历弹出序列
            stack.push(pushV[i]);
            while (stack.peek()==popV[j]&&!stack.empty()&&j< popV.length){//注意一下限制条件
                stack.pop();//i一直往后走直到和j相等，一直压入i所指向的元素
                // ，然后让j和栈顶元素比较，如果相等j往后走且栈顶一直弹出，如果所有的数都遍历完并且栈为空就返回true
                j++;
            }
        }
        return stack.empty();
    }




}
